/*
https://www.lintcode.com/problem/subsets/description
17. 子集
给定一个含不同整数的集合，返回其所有的子集

样例
如果 S = [1,2,3]，有如下的解：

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
挑战
你可以同时用递归与非递归的方式解决么？

注意事项
子集中的元素排列必须是非降序的，解集必须不包含重复的子集
*/

/*
解题思路：将每个元素都加入当前所有子集中，然后不断添加扩充子集。
*/
class Solution {
public:
    /**
     * @param nums: A set of numbers
     * @return: A list of lists
     */
    vector<vector<int>> subsets(vector<int> &nums) {
        // write your code here
        vector<vector<int> > result;
        vector<int> tmp;
        sort(begin(nums), end(nums));
        result.emplace_back(tmp);
        for (auto num : nums)
        {
            int cnt = result.size();
            for (int j = 0; j != cnt; ++j)
            {
                tmp = result[j];
                tmp.emplace_back(num);
                result.emplace_back(tmp);
            }
        }
        
        return result;
    }
};